package HashMap;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 *  题目 ：插入，删除和随机访问都是O（1）的容器
 *  题目详述 ：
 *  设计一个支持在平均时间复杂度 O(1)下，执行以下操作的数据结构：
 *
 * insert(val)：当元素 val 不存在时返回 true，并向集合中插入该项，否则返回 false 。
 * remove(val)：当元素 val 存在时返回 true，并从集合中移除该项，否则返回 false。
 * getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
 *
 */
public class OfferP30 {
    /**
     * 核心思路 ：
     * 哈希表：可以实现 插入，删除和查询某个value，时间复杂度为O（1）；
     * 问题 ：在于实现getRandom，获取随机值的话，使用哈希表就不行，但是数组的话，通过索引来获取值，可以随机获取索引值，从而来获取value；
     * 解决方法 ：（数组中存储的是需要使用的真实数据）
     * 哈希表（存储 key[值] + value[数组中的索引值]） + 数组（存储所有值）
     *
     * 插入元素 ：
     *     需要按照顺序在数组的尾部，逐步地插入元素（这样的话，在向数组插入元素后，不需要向后移动后面的index），同时在hashmap中插入对应的键值对
     * 删除元素 ：
     * （1）通过所要删除的元素值，寻找到其在数组中的索引；
     * （2）为避免 数组 删除元素后，需要向前移动所删除元素的后续index，即将数组中的index位置和数组的尾部位置的元素进行元素交换；
     * （3）同时，由于原本数组的尾部元素的index发生了变化,需要将hashmap中其key所对应value（数组中index）也进行修改；
     * 获取随机的元素 ：
     *     以数组的长度为随机数的边界，随机获取数组中的值
     */
    HashMap<Integer,Integer> map;
    ArrayList<Integer> nums;
    Random random;
    /** Initialize your data structure here. */
    public OfferP30() {
        // 初始化hashmap和arraylist（ 哈希表 和 动态数组 ）
        map = new HashMap<>();
        nums = new ArrayList<>();
        random = new Random();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }
        map.put(val,nums.size());
        nums.add(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }
        /**
         * 保证时间复杂度为O（1），即在数组中进行删除之后，后续的元素不需要前移的话， ===> 所需要删除的元素处于动态数组的最后一位
         */
        Integer index = map.get(val);  // 获取val值，所对应的索引值（代表其在动态数组中位置）
        if(index != nums.size() - 1) {
            map.put(nums.get(nums.size() - 1), index);  // 若是hashmap中key的值存在的话，即直接对其进行覆盖；否则的话，直接创建key-value键值对
            nums.set(index, nums.get(nums.size() - 1));
            // 将数组的index位置的值，设置为动态数组的最后一个元素值（相当于动态数组的index位置 与 尾部位置的元素的位置进行互换）
        }
        map.remove(val);     // 哈希表（key（元素值）- value（动态数组中所对应的索引））中，删除指定的值
        nums.remove(nums.size() - 1); // 删除位于尾部，同时经过交换过的需要进行删除的元素
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        int index = random.nextInt(nums.size());
        return nums.get(index);
    }
}
